package codeTop.简单;

/**
 * @author 挚爱之夕
 * @date 2021/9/23 - 09 - 23 - 9:58
 * @Description: codeTop
 * @Version: 1.0
 */
public class _003_合并有序链表 {
    /*
    21
    将两个升序链表合并为一个新的升序链表并返回。
    新链表是通过拼接给定的两个链表的所有节点组成的。
     */
    public static void main(String[] args) {
        ListNode l3 = new ListNode(6,null);
        ListNode l2 = new ListNode(4,l3);
        ListNode l1 = new ListNode(2,l2);
        ListNode r2 = new ListNode(5,null);
        ListNode r1 = new ListNode(1,r2);
        ListNode head = mergeTwoLists1(l1,r1);
        printList(head);
    }
    //递归
    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    //迭代
    private static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);
        ListNode prev = preHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return preHead.next;
    }
    private static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    private static void printList(ListNode head){
        while(head!=null){
            System.out.print(head.val+"->");
            head = head.next;
        }
        System.out.print("null");
    }
}
